package demo2;

import java.util.*;


public class Solution {

    public static void main(String[] args) {
        String[] board = {"XYZE", "SFZS", "XDEE"};
        String word = "XYZS";
        boolean b = exist(board, word);
        System.out.println(b);
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board string字符串一维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public static boolean exist (String[] board, String word) {
        // write code here
        char[] words = word.toCharArray();
        int m = board.length;
        int n = board[0].length();
        char[][] boards = new char[m][n];
        for(int i = 0; i < m; i++) {
            boards[i] = board[i].toCharArray();
        }
        
        return run(words, boards, m, n, 0, 0, 0);
    }

    public static boolean run(char[] words, char[][] boards, int m, int n, int i, int j, int k) {
        if(i < 0 || j < 0 || i >= m || j >= n) {
            return false;
        }

        if(k == words.length) {
            return true;
        }

        if(words[k] == boards[i][j]) {
            return run(words, boards, m, n, i+1, j, k+1) 
            || run(words, boards, m, n, i, j+1, k+1)
            || run(words, boards, m, n, i-1, j, k+1)
            || run(words, boards, m, n, i, j-1, k+1);
        }else{  
            return false;
        }
    }
}